package by2019;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class 括号匹配输出 {
/*
 * 输入字符串，字符串包含“（， ）， 【， 】， {， }”
 * 如果字符串是相互匹配的则返回true；否则返回false
 * 如：
 * 		“【（）】{}”  true
 * 		“【（】）"  false
 * 		")()"		false
 * 
 */
	public static void main(String[] args) {
		String str = "[])" ;
		Stack<String> sta = new Stack<String>() ;
		//sta.add(str);
		//sta.push(str);
		//sta.clear();
		System.out.println(sta);
		System.out.println(goOn(str));
		//System.out.println(!str.isEmpty());
	}
	
	
	/*
	 * 创建一个栈，把字符串压入栈中，如果有匹配的则将栈底元素压出，如果没有匹配则返回false
	 * 创建一个map集合，将括号对存入集合中，判断时直接利用map进行判断。
	 */
	private static boolean goOn(String str) {
		
		if("".equals(str))
			return true ;
		
		char[] sc = str.toCharArray() ;
		Stack<Character> stack = new Stack<Character>() ;
		Map<Character,Character> map = new HashMap<Character, Character>();
		map.put(')', '(');
		map.put(']', '[');
		map.put('}', '{');
		
		for(int i=0; i<sc.length; i++) {
			if(sc[i]=='(' || sc[i]=='[' || sc[i]=='{') {
				stack.push(sc[i]) ;
				System.out.println("压入"+sc[i]);
			} else{
				if( stack.empty()&&(sc[i]==')' || sc[i]==']' || sc[i]=='}'))
					return false ;
				char key = map.get(sc[i]);
				System.out.println("key="+key);
				if(key==stack.peek()) {
					System.out.println("推出"+stack.peek());
					stack.pop();
				} else {
					System.out.println(sc[i]+" 没有与之相配的括号");
					return false ;
				}
			}
		}
		if(stack.empty())
			return true ;
		return false;
	}
	
	//LeetCode 上执行耗时为1ms的程序，时间复杂度最低的
	private static boolean goOnPro(String str) {
		char[] ch = new char[str.length()+1];
		int i = 1 ;
		
		for(char c : str.toCharArray()) {
			if(c=='(' || c=='[' || c=='{') {
				ch[i++] = c ;
			} else if(c==')' && ch[--i] != '(') {
				return false ;
			} else if(c==']' && ch[--i] != '[') {
				return false ;
			} else if(c=='}' && ch[--i] != '{') {
				return false ;
			}
		}
		return i == 1 ;
	}

}
